#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2)
    // {
    //     unordered_map<int,int> map;
    //     int length1=nums1.size();
    //     int length2=nums2.size();
    //     for(int i=0;i<length2;i++)
    //     {
    //         map[nums2[i]]=-1;
    //     }
    //     stack<int> stk;
    //     stk.push(0);
    //     for(int i=1;i<length2;i++)
    //     {
    //         while(!stk.empty()&&nums2[i]>nums2[stk.top()])
    //         {
    //             map[nums2[stk.top()]]=nums2[i];
    //             stk.pop();
    //         }
    //         stk.push(i);
    //     }
    //     vector<int> result;
    //     for(int i=0;i<length1;i++)
    //     {
    //         result.push_back(map[nums1[i]]);
    //     }
    //     return result;
    // }

    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2)
    {
        int length1=nums1.size();
        int length2=nums2.size();
        vector<int> result(length1,-1);
        unordered_map<int,int> map;
        for(int i=0;i<length1;i++)
        {
            map[nums1[i]]=i;
        }
        stack<int> stk;
        stk.push(0);
        for(int i=1;i<length2;i++)
        {
            while(!stk.empty()&&nums2[i]>nums2[stk.top()])
            {
                if(map.count(nums2[stk.top()])>0)
                {
                    int index=map[nums2[stk.top()]];
                    result[index]=nums2[i];
                }
                stk.pop();
            }
            stk.push(i);
        }
        return result;
    }
};

int main()
{
    vector<int> nums1{4, 1, 2};
    vector<int> nums2{1, 3, 4, 2};
    Solution sol;
    vector<int> res = sol.nextGreaterElement(nums1, nums2);
    for (auto num : res)
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}